#ifndef KDTREE_H
#define KDTREE_H

#include "Framework.h"
#include <assimp.h>
#include <limits.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <stdlib.h>

struct bound_t {
	float min;
	float max;
};

struct BB_t {
	 
	void copy(BB_t* bb){
		memcpy(bounds, bb->bounds, 3*sizeof(bound_t));
		t_index = bb->t_index;
	}
	float xlen() const{
		return (bounds[0].max - bounds[0].min);
	}
	float ylen() const{
		return (bounds[1].max - bounds[1].min);
	}
	float zlen() const{
		return (bounds[2].max - bounds[2].min);
	}

	bound_t bounds[3];
	unsigned int t_index; // associated triangle index
};

struct triangle_t {
	aiVector3D vertices[3]; // 3 vertices
	BB_t bb; // bounding box
};
/**
  * a line struct made by aiVector3D!
  */
struct line_t{
	
	void init( const aiVector3D &pt1, const aiVector3D &pt2){
		p1 = pt1;
		p2 = pt2;
	}

	aiVector3D lineVec() const{ // no normalization
		return (p2 - p1);
	}

 
	void swap(){
		aiVector3D temp = p1;
		p1 = p2;
		p2 = temp;
	}
	
	float delta_x() const{
		return (p2.x - p1.x);
	}
	float delta_y() const{
		return (p2.y - p1.y);
	}
	float delta_z() const{
		return (p2.z - p1.z);
	}

      	float getMin(unsigned dim) const {
		switch (dim){
		case 0:
		  //if (p1.x < p2.x) return p1.x;
		  //return p2.x;
		  return std::min(p1.x, p2.x);
		case 1:
		  //if (p1.y < p2.y) return p1.y;
		  //return p2.y;
		  return std::min(p1.y, p2.y);
		case 2:
		  //if (p1.z < p2.z) return p1.z;
		  //return p2.z;
		  return std::min(p1.z, p2.z);
		default:
		  return 0.0f;
		}
	}
	
	float getMax(unsigned dim) const {
		switch (dim){
		case 0:
		  return std::max(p1.x, p2.x);
		case 1:
		  return std::max(p1.y, p2.y);
		case 2:
		  return std::max(p1.z, p2.z);
		default:
		        return 0.0f;
		}
	}

	aiVector3D p1;
	aiVector3D p2;
};

/**
  * the struct stores information of a kd-tree node
  */
struct kd_node_t {
	kd_node_t(){
		leaf_bboxes = NULL;
		l_child = NULL;
		r_child = NULL;
		leaf_bboxn = 0;
	}
	BB_t bbox;
	kd_node_t* l_child;
	kd_node_t* r_child;
	BB_t* leaf_bboxes;// only leaf node has a list of bboxes attached
	size_t leaf_bboxn;

	unsigned split_dim;
	float split_loc;
};



class KdTree {

public:
	KdTree();
	void genAllTriangles(const aiScene *scene, const aiNode* nd);
	void build_tree();
	kd_node_t* getRoot() { return _root; }

	bool cameraCollisionTest(const aiVector3D &camPos, const aiVector3D &updateVec);
	bool characterCollisionTest(const aiVector3D &camPos, const aiVector3D &updateVec);
	void render_kd_tree(kd_node_t* t_node, unsigned &itemn);

private:

	kd_node_t* _root;

	void setMeshIndices(const aiMesh *mesh);    
        BB_t computeTriBB(triangle_t& t);
        void pushTriangleBB(aiMesh *mesh, const aiMatrix4x4& modelMatrix);
	void genTriangleList(const aiScene *scene, const aiNode* node);

	std::vector<triangle_t> triangle_list;
	std::vector<unsigned> indexBuffer;

	void drawCube(const BB_t &bbox);

	aiMatrix4x4 modelMatrix;
        aiMatrix4x4 Identity;
        std::stack<aiMatrix4x4> modelMatrixStack;
       
	BB_t compute_world_bbox(const BB_t* wbboxArr, unsigned size);
	bool bboxIsTooSmall(const BB_t &bbox);
	void split(kd_node_t* me, BB_t* bboxArr, size_t bboxn);

	std::vector<aiVector3D> intersectPts; 
	std::vector<triangle_t> intersectTri;
        void triangle_intersect(const line_t &line, BB_t* bbItemList, unsigned bbItemn);
        void collide_kd_tree(kd_node_t* me , const line_t &line);

};

#endif
